名称 解决问题 Bellman-Fold 单源最短路径 迪杰斯特拉 稠密图 Floyd 多源最短路径
核心思路:
k是中转站,看一下a[i][j]是否小于dis[i][k]+dis[k][j],如果大于,a[i][j]赋值为dis[i][k]+dis[k][j],否则不变
运用Floyd算法需要用到邻接矩阵(无向图)
1.定义变量:邻接矩阵a,顶点个数n,边数m
2.输入顶点个数和边数,把邻接矩阵初始化无穷大,因为自己到自己不用走,所以代码为:
3.输出边数的起点,终点,权值
4.核心代码,实现Floyd算法